import random


def insert(lst):
    for l in range(1,len(lst)):
        ins = lst[l]
        for i in range(l,-1,-1):
            if ins < lst[i-1]:
                lst[i]=lst[i-1]
            else:
                break
        lst[i]=ins
    return lst


if __name__ == "__main__":
    n = 1000
    lst = list({random.randrange(n,10*n-1) for _ in range(n)})
    # print(insert(lst))
    print(insert(lst)==sorted(lst))